package com.fw.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {-2321,2,0,3,56,-2,123};
        int[] arrTemp = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,arrTemp);
        System.out.println(Arrays.toString(arr));


    }

    /**
     * 开始 分而治之
     * 从中间开始拆分。
     *
     */
    public static void mergeSort(int [] arr,int left,int right,int [] temp){
        if (left < right){
           int mid = (left + right) / 2;
           // 像左递归拆分
            mergeSort(arr,left,mid,temp);
            // 像右递归拆分
            mergeSort(arr,mid +1 ,right,temp);
            // 调用合并
            mergeGather(arr,left,right,mid,temp);
        }

    }


    /**
     *
     * @param arr 原始数组
     * @param left 左边开始数组的第一个索引位置
     * @param right 右边开始数组的第一个索引位置
     * @param mid  中间的所以位置
     * @param temp  临时数组，用来存放排序好的数组 最终要复制到 arr 中
     */
    public static void mergeGather(int [] arr,int left,int right,int mid,int [] temp){

        // 要做三件事

        /**
         * 1. 将左边数组拿出来于右边数组进行比较，开始置换
         * 2。 如果还剩余数组，就将剩余数据依次放入到temp 数组中
           3。 将 temp 的数组 拷贝到 arr 中
         */

        // 1。
        int l = left; // 最左边的索引地址
        int r = mid + 1; // 从右边开始的索引地址
        int t  = 0;      // 临时数组的索引位置
        while (l <= mid &&  r <= right){
            if (arr[l] <= arr[r]) {
                // 说明 左边的元素，小于右边的元素，进行置换
                temp[t] = arr[l];
                l ++;
                t ++;
            }else{
                // 反之就是 将右边的有序值 赋值到 temp
                temp[t] = arr[r];
                r ++;
                t ++;
            }
        }

        // 2。
       while (l <= mid){
           // 把剩余 左边 的数据进行填充
           temp[t] =  arr[l];
           t ++;
           l ++;
       }
       while (r <= right){
           // 把右边的数组进行填充
           temp[t] = arr[r];
           r ++;
           t ++;
       }

        // 3 将 temp copy 到 arr
        //   注意不是全部，是有规律性的。

        t = 0;
       int leftTemp = left;
       while (leftTemp <= right){
           arr[leftTemp] = temp[t];
           leftTemp ++;
           t ++;
       }
    }





}
